/*
 * bsearch_arg.c: 带用户提供指针的 bsearch 变体
 *
 * Copyright (c) 2021-2022, PostgreSQL Global Development Group
 * Copyright (c) 1990 Regents of the University of California.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation和/或其他提供的材料中。
 * 3. [已撤销 1999 年 7 月 22 日]
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse或推广基于此软件衍生的产品，
 *    除非获得特定的书面许可。
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, indirect, incidental, special, exemplary, 或后果性
 * 损害（包括但不限于获取替代商品
 * 或服务；使用、数据或利润的损失；或业务中断）所引起的损害
 * 无论在合同、严格责任或侵权（包括过失或其他）下，
 * 都不负任何责任
 * 即使被告知此类损害的可能性。
 *
 * src/port/bsearch_arg.c
 */

#include "c.h"

/*
 * 执行二分查找。
 *
 * 下面的代码有点狡猾。在比较失败后，我们通过向左或向右移动来将工作分成两半。如果 lim 是奇数，向左移动只需将 lim 对半分：例如，当 lim 为 5 时，我们查看第 2 个项，因此我们将 lim 改为 2，这样我们将查看第 0 和第 1 项。如果 lim 是偶数，同样适用。如果 lim 是奇数，向右移动同样需要将 lim 对半分，这次将基准向上移动一项超过 p：例如，当 lim 为 5 时，我们将基准改为第 3 个项，并将 lim 设置为 2，这样我们将查看第 3 和第 4 个项。然而，如果 lim 是偶数，我们必须先将它减一再对半分：例如，当 lim 为 4 时，我们仍然查看第 2 个项，因此我们必须将 lim 设置为 3，然后对半分，得到 1，这样我们将只查看第 3 个项。
 */
void * bsearch_arg(const void *fc_key, const void *fc_base0,
			size_t fc_nmemb, size_t fc_size,
			int (*fc_compar) (const void *, const void *, void *),
			void *fc_arg)
{
	const char *fc_base = (const char *) fc_base0;
	size_t		fc_lim;
	int			fc_cmp;
	const void *fc_p;

	for (fc_lim = fc_nmemb; fc_lim != 0; fc_lim >>= 1)
	{
		fc_p = fc_base + (fc_lim >> 1) * fc_size;
		fc_cmp = (*fc_compar) (fc_key, fc_p, fc_arg);
		if (fc_cmp == 0)
			return (void *) fc_p;
		if (fc_cmp > 0)
		{						/* key > p: move right */
			fc_base = (const char *) fc_p + fc_size;
			fc_lim--;
		}						/* else move left */
	}
	return (NULL);
}
